package com.atguigu.srb.base.algorithm;

import org.springframework.util.CollectionUtils;
import org.springframework.util.StopWatch;

import java.util.*;

/**
 * @ClassName Solution5
 * @Describe
 * @Author Wangchengshan
 * @Date 2023/5/24 10:51
 * @Version 1.0
 **/
public class Solution6 {

    //给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。
    //一开始你在下标 0 处。每一步，你最多可以往前跳 k 步，但你不能跳出数组的边界。
    //你的目标是到达数组最后一个位置（下标为 n - 1 ），你的 得分 为经过的所有数字之和。
    //请你返回你能得到的 最大得分 。
    //
    //输入：nums = [1,-1,-2,4,-7,3], k = 2
    //输出：7
    //
    //输入：[10,-5,-2,4,0,3], k = 3
    //输出：17
    public static int maxResult(int[] nums, int key) {
        if (nums.length == 1) {
            return nums[0];
        }
//        Arrays.stream(nums).max().getAsInt()
//        key是数，value是索引
        Map<Integer, Integer> map = new HashMap<>();
        int sum = nums[0];
        List<Integer> indexList = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        int i = 1;
        while (i < nums.length) {
            if (i == 5) {
                System.out.println(1);
            }
            if (key > map.keySet().size()) {
                indexList.add(i);
                list.add(nums[i]);
                map.put(i, nums[i]);
                i++;
                if(i == nums.length - 1){
                    sum = sum + nums[nums.length-1];
                }
            } else {
                int max = Collections.max(map.values());
                sum = sum + max;
//                int integer = list.indexOf(max);//获取最大值的最大索引
                int integer = -1;//获取最大值的最大索引
                for (int i1 = list.size()-1; i1 >=0 ; i1--) {
                    if(list.get(i1) == max){
                        integer = i1;
                        break;
                    }
                }
                List<Integer> removeList = new ArrayList<>();//把小于最小索引+1的从map中移除
                for (int i1 = 0; i1 < list.size(); i1++) {
                    if (i1 <= integer) {
                        //TODO indexList 3,4   indexList.get(integer) == 4
                        removeList.add(indexList.get(i1));
//                        removeList.add(list.get(i1));
                    }
                }
                if (!CollectionUtils.isEmpty(removeList)) {
                    i = indexList.get(integer) + 1;
                }
                if (!CollectionUtils.isEmpty(removeList)) {
                    for (Integer integer1 : removeList) {
                        map.remove(integer1);
                    }
                }
                list.clear();
                indexList.clear();
            }
        }
        return sum;
    }


    public static void main(String[] args) {
        int[] nums1 = new int[]{10, -5, -2, 4, 0, 3};//17
        int[] nums2 = new int[]{10, -5, -5, -7, -6, 3}; //2
        int[] nums5 = new int[]{10, -5, -5, -6, -7, 3}; //2
        int[] nums3 = new int[]{1,-1,-2,4,-7,3};
        int[] nums4 = new int[]{1, 1, 1, 2, 4};//6
        StopWatch sw = new StopWatch("time: ");
        sw.start();
        int i = maxResult(nums1, 3);
        sw.stop();
        System.out.println("result " + i);
        System.out.println(sw.prettyPrint());
    }
}
